<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2826：Minecraft的世界末日</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Minecraft的世界末日</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">Minecraft的世界末日</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                Minecraft的世界末日                </h1>
                <p>时间限制：30s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div><span style="font-size: medium">邪恶的PureDark星球的居民把曾经美丽的草原、森林、海洋、高山、沙漠变成了由工业MOD驱动</span></div>
<div><span style="font-size: medium">的各类机器所构成的钢铁城市。可惜，这些居民或是因为水平不足，亦或是抱着一种不负责任的心态，</span><span style="font-size: medium">无数次核弹的爆炸以及各类核电事故，加之植被被毁、空气污染，整个星球的环境已经恶化到了不可挽</span><span style="font-size: medium">回的地步。就在这个时候，平日里被各种OI题目虐得死去活来的沙茶，突然人品爆发，发明出一种机器，这种</span><span style="font-size: medium">机器能够把环境中的污染物转变成一种特殊的粒子&mdash;&mdash;沙茶粒子(Sandy-tea Particle，简称STP)，也可以</span><span style="font-size: medium">将这种粒子放出重新变成污染物。PureDark星球的居民发现，这是收集这种危险污染物的唯一方式。而</span><span style="font-size: medium">由于污染物的量过于巨大，通过收集污染物的方式无法阻止环境恶化，因此人们并不重视这台机器，也</span><span style="font-size: medium">没有人愿意协同沙茶完成自己的伟大设计，因此沙茶来到地球，找到了身为OI大牛的你。</span><span style="font-size: medium">因为Minecraft世界中没有任何物理可言，沙茶可以通过一种叫做Redstone的物质无限地获取能源</span><span style="font-size: medium">供机器运转而不需要付出任何费用或是高能的STP，同时物质的转化也不再满足质量守恒的规律。也就是</span><span style="font-size: medium">说，在某一天将污染物转化为STP，在另一天可能可以以不同的比例转化回污染物。沙茶准备利用这种转</span><span style="font-size: medium">化的比例差来产生更多的STP，因为他预感到这种粒子可以起到拯救世界的作用，虽然他不知道如何用</span><span style="font-size: medium">STP来拯救世界。很可惜沙茶终究是沙茶，他的机器能力非常有限，每天最多只能够转化污染物 Gi</span><span style="font-size: medium">&nbsp;mol或是释放污染</span><span style="font-size: medium">物 Di mol（这些值能事先被预测出来），转化和释放污染物不能在同一天进行，且转化的污染物的物质</span><span style="font-size: medium">的量必须是整数。机器每次进行物质转化后，需要等待T天使设备冷却，冷却过程中不能再进行物质转</span><span style="font-size: medium">化。沙茶的机器有一个用于存储污染物的大仓，它的容积当然不是无限大的，最多能存储C mol 污染物。</span><span style="font-size: medium">每次实验结束时，机器中的污染物必须被清空，沙茶可不愿意冒机器爆炸的险。也是因为Minecraft世界</span><span style="font-size: medium">没有任何物理可言，STP粒子可以以任意的密度存在，也就是说机器中的STP粒子可以无限多。同时，</span><span style="font-size: medium">机器中STP粒子的物质的量可以为0、为正整数，甚至可以为负整数。</span><span style="font-size: medium">现在，沙茶想做M次实验来测试机器的稳定性。在每次实验开始时，他拥有的STP的物质的量为</span><span style="font-size: medium">0。他预感到了第i天每摩尔污染物需要STP的物质的量Ai</span><span style="font-size: medium">以及这一天每摩尔污染物能转化成的STP的物</span><span style="font-size: medium">质的量Bi</span><span style="font-size: medium">，以及前文提到的 Gi</span><span style="font-size: medium">和Di</span><span style="font-size: medium">&nbsp;。请帮他算出他每次实验能获得的STP的最大值。</span></div></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium">&nbsp;</span><span style="font-size: medium">第1行是一个正整数M，表示实验的次数。</span></p>
<div><span style="font-size: medium">对于每次实验，第1行是三个正整数N，T，C，分别表示实验的天数、设备冷却时间和污染物存储</span><span style="font-size: medium">器的容量。第2~5行分别有N个正整数，每行分别是A1、A2&hellip;&hellip;AN，B1、B2&hellip;&hellip;BN，G1、G2&hellip;&hellip;</span><span style="font-size: medium">GN，D1、D2&hellip;&hellip;DN，意义如前文所述。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>输出格式</h3><p><div><span style="font-size: medium">M行，每行一个整数，第i行的整数表示沙茶在第i次实验中能获得的最大STP的物质的量。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>样例输入</h3><pre> 
1
10 1 10
1 1 1 5 5 10 10 10 10 10
1 2 3 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
</pre><hr/><h3>样例输出</h3><pre>14
样例解释
一个最优方案为：在第1、3天各消耗1 mol STP转化为1 mol 污染物，在第7、9天分别将1 mol
污染物转化为7、9 mol STP，整个实验结束时有STP (7+9-1-1) mol=14 mol。
 
</pre><hr/><h3>提示</h3><p><div style="text-align: left; line-height: normal; font-family: arial, verdana, sans-serif; font-size: medium"><span style="line-height: 21px; font-family: 黑体; font-size: 14px">0&le;Ai,Bi,Gi,Di&le;100</span></div>
<p>有M&le;10，O&le;T＜N&le;3000，1&le;C&le;3000</p></p><hr/><h3>题目来源</h3><p>湖北省队互测</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2826" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2826" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>